package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         154,
		Discription: "寻找升序数组旋转后的最小值（有重复元素）",
		Level:       3,
		Labels: map[string]int{
			"二分查找": 1,
			"去重": 1,
		},
	})
}

func FindMin2(nums []int) int {
	left := 0
	right := len(nums) - 1
	for left < right {
		mid := left + (right-left)/2
		//清除两边重复的元素
		for left < mid && nums[left] == nums[mid] {
			left++
		}
		for right > mid && nums[right] == nums[mid] {
			right--
		}

		//一定得<=，因为如果nums[mid]==nums[right]，说明right和mid是重合的，此时mid也有可能是最终答案
		if nums[mid] <= nums[right] {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return nums[left]
}